home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 2 / Atari Mega Archive CD - Volume 2.iso / minix / up1510b.tgz / up1510b / src / commands / diff.c < prev    next >
C/C++ Source or Header  |  1990-07-19  |  6KB  |  346 lines
  1. /* diff  - print differences between 2 files      Author: Erik Baalbergen */
  2.  
  3. /* Poor man's implementation of diff(1)
  4.  - no options available
  5.  - may give more output than other diffs, due to the straight-forward algorithm
  6.  - runs out of memory if the differing chunks become too large
  7.  - input line length should not exceed LINELEN; longer lines are truncated,
  8.    while only the first LINELEN characters are compared
  9.  
  10.  - Bug fixes by Rick Thomas Sept. 1989
  11.  
  12.  Please report bugs and suggestions to erikb@cs.vu.nl
  13. */
  14.  
  15. #include <stdio.h>
  16.  
  17. #define LINELEN 128
  18.  
  19. FILE *fopen();
  20.  
  21. char *prog;
  22. int diffs = 0;
  23.  
  24. main(argc, argv)
  25. char **argv;
  26. {
  27.   FILE *fp1 = NULL, *fp2 = NULL;
  28.  
  29.   prog = *argv++;
  30.   if (argc != 3) fatal("Usage: %s file1 file2", prog);
  31.   if (strcmp(argv[0], "-") == 0)
  32.     fp1 = stdin;
  33.   else if (strcmp(argv[1], "-") == 0)
  34.     fp2 = stdin;
  35.   if (fp1 == NULL && (fp1 = fopen(argv[0], "r")) == NULL)
  36.     fatal("can't read %s", argv[0]);
  37.   if (fp2 == NULL && (fp2 = fopen(argv[1], "r")) == NULL)
  38.     fatal("can't read %s", argv[1]);
  39.   diff(fp1, fp2);
  40.   exit(diffs > 0);
  41. }
  42.  
  43. fatal(fmt, s)
  44. char *fmt, *s;
  45. {
  46.   fprintf(stderr, "%s: ", prog);
  47.   fprintf(stderr, fmt, s);
  48.   fprintf(stderr, "\n");
  49.   exit(2);
  50. }
  51.  
  52. /* The line module */
  53. char *malloc();
  54. char *fgets();
  55.  
  56. struct line {
  57.   struct line *l_next;
  58.   char l_text[LINELEN + 2];
  59.   char l_eof;
  60. };
  61.  
  62. struct line *freelist = 0;
  63. #define stepup(ll) ( ((ll) && ((ll)->l_eof==0)) ? (ll)->l_next : (ll) )
  64.  
  65. struct line *
  66.  new_line()
  67. {
  68.   register struct line *l;
  69.  
  70.   if (l = freelist)
  71.     freelist = freelist->l_next;
  72.   else if ((l = (struct line *) malloc(sizeof(struct line))) == 0)
  73.     fatal("out of memory");
  74.   return l;
  75. }
  76.  
  77. free_line(l)
  78. register struct line *l;
  79. {
  80.   l->l_next = freelist;
  81.   freelist = l;
  82. }
  83.  
  84. int equal_line(l1, l2)
  85. struct line *l1, *l2;
  86. {
  87.   if (l1 == 0 || l2 == 0)
  88.     return(0);
  89.   else if (l1->l_eof || l2->l_eof)
  90.     return(l1->l_eof == l2->l_eof);
  91.   else
  92.     return(strcmp(l1->l_text, l2->l_text) == 0);
  93. }
  94.  
  95. int equal_3(l1, l2)
  96. struct line *l1, *l2;
  97. {
  98.   register int i, ansr;
  99.  
  100.   ansr = 1;
  101. #ifdef DEBUG
  102.   if (l1 == 0)
  103.     fprintf(stderr, "\t(null)\n");
  104.   else if (l1->l_eof)
  105.     fprintf(stderr, "\t(eof)\n");
  106.   else
  107.     fprintf(stderr, "\t%s", l1->l_text);
  108.   if (l2 == 0)
  109.     fprintf(stderr, "\t(null)\n");
  110.   else if (l2->l_eof)
  111.     fprintf(stderr, "\t(eof)\n");
  112.   else
  113.     fprintf(stderr, "\t%s", l2->l_text);
  114. #endif
  115.   for (i = 0; i < 3; ++i) {
  116.     if (!equal_line(l1, l2)) {
  117.         ansr = 0;
  118.         break;
  119.     }
  120.     l1 = stepup(l1);
  121.     l2 = stepup(l2);
  122.   }
  123. #ifdef DEBUG
  124.   fprintf(stderr, "\t%d\n", ansr);
  125. #endif
  126.   return(ansr);
  127. }
  128.  
  129. struct line *
  130.  read_line(fp)
  131. FILE *fp;
  132. {
  133.   register struct line *l = new_line();
  134.   register char *p;
  135.   register int c;
  136.  
  137.   (p = &(l->l_text[LINELEN]))[1] = '\377';
  138.   l->l_eof = 0;
  139.   if (fgets(l->l_text, LINELEN + 2, fp) == NULL) {
  140.     l->l_eof = 1;
  141.     l->l_text[0] = 0;
  142.   } else if ((p[1] & 0377) != 0377 && *p != '\n') {
  143.     while ((c = fgetc(fp)) != '\n' && c != EOF) {
  144.     }
  145.     *p++ = '\n';
  146.     *p = '\0';
  147.   }
  148.   l->l_next = 0;
  149.   return l;
  150. }
  151.  
  152. /* File window handler */
  153. struct f {
  154.   struct line *f_bwin, *f_ewin;
  155.   struct line *f_aside;
  156.   int f_linecnt;        /* line number in file of last advanced line */
  157.   FILE *f_fp;
  158. };
  159.  
  160. advance(f)
  161. register struct f *f;
  162. {
  163.   register struct line *l;
  164.  
  165.   if (l = f->f_bwin) {
  166.     if (f->f_ewin == l)
  167.         f->f_bwin = f->f_ewin = 0;
  168.     else
  169.         f->f_bwin = l->l_next;
  170.     free_line(l);
  171.     (f->f_linecnt)++;
  172.   }
  173. }
  174.  
  175. aside(f, l)
  176. struct f *f;
  177. struct line *l;
  178. {
  179.   register struct line *ll;
  180.  
  181.   if (l == 0) return;
  182.   if (ll = l->l_next) {
  183.     while (ll->l_next) ll = ll->l_next;
  184.     ll->l_next = f->f_aside;
  185.     f->f_aside = l->l_next;
  186.     l->l_next = 0;
  187.     f->f_ewin = l;
  188.   }
  189. }
  190.  
  191. struct line *
  192.  next(f)
  193. register struct f *f;
  194. {
  195.   register struct line *l;
  196.  
  197.   if (l = f->f_aside) {
  198.     f->f_aside = l->l_next;
  199.     l->l_next = 0;
  200.   } else
  201.     l = read_line(f->f_fp);
  202.   if (l) {
  203.     if (f->f_bwin == 0)
  204.         f->f_bwin = f->f_ewin = l;
  205.     else {
  206.         if (f->f_ewin->l_eof && l->l_eof) {
  207.             free_line(l);
  208.             return(f->f_ewin);
  209.         }
  210.         f->f_ewin->l_next = l;
  211.         f->f_ewin = l;
  212.     }
  213.   }
  214.   return l;
  215. }
  216.  
  217. init_f(f, fp)
  218. register struct f *f;
  219. FILE *fp;
  220. {
  221.   f->f_bwin = f->f_ewin = f->f_aside = 0;
  222.   f->f_linecnt = 0;
  223.   f->f_fp = fp;
  224. }
  225.  
  226. update(f, s)
  227. register struct f *f;
  228. char *s;
  229. {
  230.   while (f->f_bwin && f->f_bwin != f->f_ewin) {
  231.     printf("%s%s", s, f->f_bwin->l_text);
  232.     advance(f);
  233.   }
  234. }
  235.  
  236. /* Diff procedure */
  237. diff(fp1, fp2)
  238. FILE *fp1, *fp2;
  239. {
  240.   struct f f1, f2;
  241.   struct line *l1, *s1, *b1, *l2, *s2, *b2;
  242.   register struct line *ll;
  243.  
  244.   init_f(&f1, fp1);
  245.   init_f(&f2, fp2);
  246.   l1 = next(&f1);
  247.   l2 = next(&f2);
  248.   while ((l1->l_eof == 0) || (l2->l_eof == 0)) {
  249.     if (equal_line(l1, l2)) {
  250.   equal:
  251.         advance(&f1);
  252.         advance(&f2);
  253.         l1 = next(&f1);
  254.         l2 = next(&f2);
  255.         continue;
  256.     }
  257.     s1 = b1 = l1;
  258.     s2 = b2 = l2;
  259.     /* Read several more lines */
  260.     next(&f1);
  261.     next(&f1);
  262.     next(&f2);
  263.     next(&f2);
  264.     /* Start searching */
  265. search:
  266.     next(&f2);
  267.     ll = s1;
  268.     do {
  269.         if (equal_3(ll, b2)) {
  270.             l1 = ll;
  271.             l2 = b2;
  272.             aside(&f1, ll);
  273.             aside(&f2, b2);
  274.             differ(&f1, &f2);
  275.             goto equal;
  276.         }
  277.         if (ll->l_eof) break;
  278.         ll = stepup(ll);
  279.     } while (ll);
  280.     b2 = stepup(b2);
  281.  
  282.     next(&f1);
  283.     ll = s2;
  284.     do {
  285.         if (equal_3(b1, ll)) {
  286.             l1 = b1;
  287.             l2 = ll;
  288.             aside(&f2, ll);
  289.             aside(&f1, b1);
  290.             differ(&f1, &f2);
  291.             goto equal;
  292.         }
  293.         if (ll->l_eof) break;
  294.         ll = stepup(ll);
  295.     } while (ll);
  296.     b1 = stepup(b1);
  297.  
  298.     goto search;
  299.   }
  300.  
  301.   /* Both of the files reached EOF */
  302. }
  303.  
  304. differ(f1, f2)
  305. register struct f *f1, *f2;
  306. {
  307.   int cnt1 = f1->f_linecnt, len1 = wlen(f1), cnt2 = f2->f_linecnt, len2 = wlen(f2);
  308.  
  309.   if ((len1 = wlen(f1)) || (len2 = wlen(f2))) {
  310.     if (len1 == 0) {
  311.         printf("%da", cnt1);
  312.         range(cnt2 + 1, cnt2 + len2);
  313.     } else if (len2 == 0) {
  314.         range(cnt1 + 1, cnt1 + len1);
  315.         printf("d%d", cnt2);
  316.     } else {
  317.         range(cnt1 + 1, cnt1 + len1);
  318.         putchar('c');
  319.         range(cnt2 + 1, cnt2 + len2);
  320.     }
  321.     putchar('\n');
  322.     if (len1) update(f1, "< ");
  323.     if (len1 && len2) printf("---\n");
  324.     if (len2) update(f2, "> ");
  325.     diffs++;
  326.   }
  327. }
  328.  
  329. wlen(f)
  330. struct f *f;
  331. {
  332.   register cnt = 0;
  333.   register struct line *l = f->f_bwin, *e = f->f_ewin;
  334.  
  335.   while (l && l != e) {
  336.     cnt++;
  337.     l = l->l_next;
  338.   }
  339.   return cnt;
  340. }
  341.  
  342. range(a, b)
  343. {
  344.   printf(((a == b) ? "%d" : "%d,%d"), a, b);
  345. }
  346.